1. Field of the Invention
The present invention relates to communication and computer networks, and, in particular, to use of variable-stride-block processing in multi-pattern matching for content-inspection system applications.
2. Description of the Related Art
This section introduces aspects that may help facilitate a better understanding of the invention(s). Accordingly, the statements of this section are to be read in this light and are not to be understood as admissions about what is or is not in the prior art.
Multi-pattern matching is a key function used by content-inspection systems such as signature-based network-intrusion detection and prevention systems (NIDS/NIPS or NIDPS). Such systems depend on reliable real-time detection of specific signatures or patterns within network traffic to determine whether the traffic may potentially be harmful to the network or components of the network, including hosts.
Typically, content-inspection systems may search for many such signatures concurrently. As line rates increase beyond 10 Gbps, methods for efficiently handling multi-pattern matching have become increasingly important.
Historically, pattern matching has been accomplished using a deterministic finite automaton (DFA). A DFA is a finite state machine where, for each state and input symbol, there is one and only one transition to a next state. Information on DFAs may be found in Gill, A., Introduction to the Theory of Finite-State Machines, McGraw-Hill, 1962, incorporated herein by reference in its entirety.
In a basic type of DFA-based pattern matching, network traffic streams are processed one byte or character at a time. Such DFAs require n states to process n single-byte patterns and require t transitions per state, where t is the number of symbols in the pattern alphabet. However, processing one byte per clock at the line rates of modern networks is too slow.
One way of improving upon the throughput of the fundamental DFA is by scanning multiple bytes (i.e., a block) of the input data stream in each matching step. While this block-oriented DFA approach provides a speedup relative to the byte-oriented DFA proportional to the number of bytes in a block, it presents other issues. In particular, since a pattern may start or end at any offset in a block, a block-oriented DFA may need either to (1) be repeated s times, where s is the block size or “stride” of the DFA, or (2) provide many more transitions per state.
For example, in a first block-oriented DFA approach to pattern matching, patterns are divided into s-byte blocks, and the blocks are used to construct the DFA. This results in a DFA with fewer states and transitions than a corresponding byte-oriented DFA for the same pattern. However, s instances of the DFA need to run in parallel, each accepting the same input data stream with an one-byte offset (to ensure that no patterns are overlooked). If the input stream is . . . babbaba . . . , the sequence . . . |ba|bb|ab|a . . . and its one-byte shifted version . . . b|ab|ba|ba| . . . both need to be processed to ensure that a match is not missed. With this approach, higher throughputs are achieved at the expense of higher memory-bandwidth usage (the result of running s instances of the matching engine in parallel), which memory-bandwidth needs grow in proportion to the block size s.
Alternatively, one can build a single DFA for which the transitions account for all the possible s-byte patterns that can occur in the stream. By using a larger DFA, a single instance of the matching engine can be used to scan the input data stream without the possibility of missed matches. The throughput gain in this case is at the cost of higher memory usage, rather than higher memory bandwidth. Note also that the number of transitions from any state can be as large as ts, where t is the size of the alphabet. Indeed, for NIDS signature sets that use the English alphabet where t=26, memory usage becomes prohibitively high even for a block size s of two bytes.
Thus, a fundamental problem with existing pattern-matching approaches is excessive memory or memory-bandwidth requirements, particularly for systems that can run at the line-rate of current and anticipated network interfaces.